package dynProg.solvers;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import dynProg.ArrayHelper;
import dynProg.Solver;

/**
 * 
 * @author Stephan Veenstra
 * @version 1.0
 */
public class RecursiveSolver implements Solver {

	@Override
	public boolean solve(int[] numbers, int sum) {
		if( sum == 0 ) return true;			// Je kunt altijd 0 maken door niets op te tellen
        if( numbers.length == 0 ) return false; // Zonder getalen is er geen som anders dan 0

        int n = numbers.length - 1;	// Bepaal de lengte van het subprobleem
        int[] subProblem = new int[n]; // Maak het sub probleem array
        for(int i = 0; i < n; i++){ // vul het subProbleem
            subProblem[i] = numbers[i];
        }

        if(solve(subProblem, sum) || solve(subProblem, sum - numbers[n])) // Roep de methode nog twee keer aan voor het subprobleem
        	return true;												// 1 keer voor sum en een keer voor sum - laatste getal van numbers
        else 
        	return false;
        
	}

}
